Implementations of elliptic curve cryptosystems may be vulnerable to side-channel attacks ([1], [2]) where adversaries can use power consumption measurements or similar observations to derive information on secret scalars e in point multiplications eP.
One distinguishes between differential side-channel attacks, which require correlated measurements from multiple point multiplications, and simple side-channel attacks, which directly interpret data obtained during a single point multiplication. Randomization can be used as a countermeasure against differential side-channel attacks.
In particular, for elliptic curve cryptography, projective randomization is a simple and effective tool ([3]):
If (X, Y, Z) represents the point whose affine coordinates are (X/Z2, Y/Z.3) another representation of the same point that cannot be predicted by the adversary is obtained by substituting (r2X, r3Y, rZ) with a randomly chosen secret non-zero field element r. (When starting from an affine representation (X,Y), this simplifies to (r2X, r3Y, r).)
Simple side-channel attacks can be easily performed because usually the attacker can tell apart point doublings from general point additions.
Thus point multiplication should be implemented using a fixed sequence of point operations that does not depend on the particular scalar.
Note that it is reasonable to assume that point addition and point subtraction are uniform to the attacker as point inversion is nearly immediate (dummy inversions can be inserted to obtain the same sequence of operations for point additions as for point subtractions).
Various point multiplication methods have been proposed that use an alternating sequence of doublings and additions:
The simplest approach uses a binary point multiplication method with dummy additions inserted to avoid dependencies on scalar bits ([3]); however as noted in [4] it may be easy for adversaries to determine which additions are dummy operations, so it is not clear that this method provides sufficient security. For odd scalars, a variant of binary point multiplication can be used where the scalar is represented in balanced binary representation (digits −1 and +1) ([5]). Also Montgomery's binary point multiplication method ([6]), which maintains an invariant Q1−Qo=P while computing eP using two variables Qo, Q1, can be adapted for implementing point multiplication with a fixed sequence of point operations ([7], [8], [9], [10], [11]).
With this approach, specific techniques can be used to speed up point arithmetic:
The doubling and addition steps can be combined; y-coordinates of points may be omitted during the computation ([6], [9], [10], [11]); and on suitable hardware, parallel execution can be conveniently used for improved efficiency ([10], [11]).
All of the above point multiplication methods are binary. Given sufficient memory, efficiency can be improved by using 2w-ary point multiplication methods. Here, the scalar e is represented in base 2w using digits bi from some digit set B:
  e  =            ∑              0        ≤        i        ≤        l              ⁢                  ⁢                  b        i            ⁢              2        wi            
A simple way to obtain a uniform sequence of doublings and additions (namely, one addition after w doublings in the main loop of the point multiplication algorithm) is to use 2w-ary point multiplication as usual (first compute and store bP for each bεB, then compute eP using this precomputed table), but to insert a dummy addition whenever a zero digit is encountered.
However, as noted above for the binary case, the dummy addition approach may not be secure.
This problem can be avoided (given w≧2) by using a representation of e without digit value 0, such asB={−2w, 1, 2, . . . , 2w−1}as proposed in [4], orB={−2w, ±1,±2, . . . , ±(2w−2),2w−1}for improved efficiency as proposed in [12].
A remaining problem in the method of [4] and [12] is that the use of a fixed table may allow for statistical attacks: If the same point from the table is used in a point addition whenever the same digit value occurs, this may help adversaries to find out which of the digits b1, have the same value (cf. the attacks on modular exponentiation using fixed tables in [13] and [14]).
This problem can be countered by performing, whenever the table is accessed, a projective randomization of the table value that has been used.
This will avoid a fixed table, but at the price of reduced efficiency.